题面

解题思路

贪心+反悔机制

分析

用 $priority\ queue$ 维护最小值，对于每个已选择的点添加值为 $a{l{pos}}+a{r{pos}}-a_{pos}$ 的点，用双向链表维护左右即可

warning

1、$a_0\ \&\ a_n=+\infty$

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define paLi pair<LL,int>//pair存val以及pos
#define Mp make_pair
#define N 100003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,m,pos,l[N],r[N];
LL a[N],ans;
bool vis[N];
priority_queue<paLi>p;//prio默认大根堆
paLi c;
int main() {
    rint i;n=read()-1,m=read();
    for(i=1;i<=n+1;i++) a[i]=read();
    for(i=1;i<=n;i++) a[i]=a[i+1]-a[i],l[i]=i-1,r[i]=i+1,p.push(Mp(-a[i],i));
    a[n+1]=a[0]=inf;
    while(m--) {
        do c=p.top(),p.pop(); while(vis[c.second]);
        pos=c.second,ans-=c.first,
        vis[l[pos]]=vis[r[pos]]=1;//标记左右被取并添加反悔点
        a[pos]=a[l[pos]]+a[r[pos]]-a[pos];
        p.push(Mp(-a[pos],pos));
        l[pos]=l[l[pos]],r[l[pos]]=pos,
        r[pos]=r[r[pos]],l[r[pos]]=pos;
    }printf("%lld",ans);
    return 0;
}

devil.